#!/usr/bin/python env


class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0 or n == 1 or n == 2:
            return n

        a = 1
        b = 2

        for i in range(n - 2):
            a, b = b, a+b

        return b


if __name__ == "__main__":
    s = Solution()
    x = s.climbStairs(4)
    print x
